package com.liuzhilong.infrastructure.framework.algorithms.algorithms.sort.base;

import static com.liuzhilong.infrastructure.framework.algorithms.algorithms.sort.SortCommon.exch;
import static com.liuzhilong.infrastructure.framework.algorithms.algorithms.sort.SortCommon.less;

/**
 * <h1>希尔排序</h1>
 * <p>
 *     一种升级版的插入排序.<br>
 *     插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。<br>
 *      但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
 * </p>
 * <p>
 *  主要思想：从插入排序的优劣势进行处理。先使用间隔一定数量（比如h）进行插入排序，把数据处理成大致有序。这样能解决插入排序的劣势，并恰好构建成插入排序的优势。
 *  然后，降低h，再次继续间隔的插入排序。
 *  <br>
 *  看起来好像比插入排序复制很多。但是在实际的使用中，效率是比单纯的插入排序要高的。并且数据量越大，优势越大。说明对于插入排序来说，一定上的有序，会带来非常大的提升。
 *  速度是插入排序的百倍以上。
 * </p>
 * <pre>
 *
 *  希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
 *
 *  希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。
 *
 *  希尔排序按其设计者希尔（Donald Shell）的名字命名，该算法由希尔 1959 年公布。一些老版本教科书和参考手册把该算法命名为 Shell-Metzner，即包含 Marlene Metzner Norton 的名字，但是根据 Metzner 本人的说法，“我没有为这种算法做任何事，我的名字不应该出现在算法的名字中。”
 *
 *
 * </pre>
 * 时间负载度在O
 */
public class ShellSort {


    public static void sort(Comparable[] arrays) {
        //构架合适的h
        int h=1;
        while(h<arrays.length/3){
            h = h * 3 + 1;
        }
        //h梯度下降；并且每下降一次，执行一次插入排序；直到h<1.
        while(h>=1){
            for (int i = h; i <arrays.length ; i++) {
                for (int j = i; j >=h && less(arrays[j],arrays[j-h]); j-=h) {
                    exch(arrays,j,j-h);
                }
            }
            //下降
            h=h/3;
        }






    }








}
